package datastructure.Graph;


import java.util.*;

/**
 * Description：邻接表实现图算法
 * Author: zhangc
 * Date：2017/7/21 20:54
 */
public class AdjacencyList {

    private VNode[] nodes;

    public VNode[] getNodes() {
        return nodes;
    }

    public int getVertexNums() {
        return vertexNums;
    }

    private int vertexNums;

    private AdjacencyList(int vertexNums) {
        this.vertexNums = vertexNums;
        this.nodes = new VNode[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            nodes[ i ] = new VNode(i);
        }
    }

    public static AdjacencyList createAdjustList(int[][] matrix) {
        AdjacencyList adjacencyList = new AdjacencyList(matrix.length);
        AceNode tempAce;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[ i ][ j ] > 0) {
                    if (adjacencyList.nodes[ i ].firstAce == null) {
                        adjacencyList.nodes[ i ].firstAce = setAceNode(matrix[ i ][ j ], adjacencyList.nodes[ j ]);
                    } else {
                        tempAce = adjacencyList.nodes[ i ].firstAce;
                        while (tempAce.nextAce != null)
                            tempAce = tempAce.nextAce;
                        tempAce.nextAce = setAceNode(matrix[ i ][ j ], adjacencyList.nodes[ j ]);
                    }
                }
            }
        }
        return adjacencyList;
    }

    private static AceNode setAceNode(int weight, VNode vNode) {
        AceNode aceNode = new AceNode();
        aceNode.weight = weight;
        aceNode.vNode = vNode;
        return aceNode;
    }

    public List<VNode> DFSNoRecursive(int index) {
        if (index < 0 || nodes.length <= index)
            return null;

        boolean[] visit = new boolean[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            visit[ i ] = false;
        }

        List<VNode> list = new ArrayList<>();
        Stack<VNode> stack = new Stack<>();
        stack.push(nodes[ index ]);
        VNode temp;
        AceNode tempAce;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            if (!visit[ temp.nodeNo ]) {
                list.add(temp);
                visit[ temp.nodeNo ] = true;
            }
            tempAce = temp.firstAce;
            while (tempAce != null) {
                stack.push(tempAce.vNode);
                tempAce = tempAce.nextAce;
            }
        }
        return list;
    }

    public List<VNode> DFS(int index) {
        if (nodes == null || nodes.length <= 0)
            return null;
        List<VNode> list = new ArrayList<>();
        boolean[] visit = new boolean[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            visit[ i ] = false;
        }
        DFS(list, visit, index);
        return list;
    }

    private void DFS(List<VNode> list, boolean[] visit, int index) {
        list.add(nodes[ index ]);
        visit[ index ] = true;
        AceNode ace = nodes[ index ].firstAce;
        while (ace != null) {
            if (!visit[ ace.vNode.nodeNo ]) {
                DFS(list, visit, ace.vNode.nodeNo);
            }
            ace = ace.nextAce;
        }
    }

    public List<VNode> BFS(int index) {
        if (nodes == null || nodes.length <= 0)
            return null;
        List<VNode> list = new ArrayList<>();
        boolean[] visit = new boolean[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            visit[ i ] = false;
        }
        BFS(list, visit, index);
        return list;
    }

    private void BFS(List<VNode> list, boolean[] visit, int index) {
        Queue<VNode> queue = new LinkedList<>();
        queue.add(nodes[ index ]);
        VNode temp;
        AceNode aceNode;
        while (!queue.isEmpty()) {
            temp = queue.remove();
            if (!visit[ temp.nodeNo ]) {
                list.add(temp);
                visit[ temp.nodeNo ] = true;
            }
            aceNode = temp.firstAce;
            while (aceNode != null) {
                queue.add(aceNode.vNode);
                aceNode = aceNode.nextAce;
            }
        }
    }

    public List<VNode> topOrder() {
        List<VNode> list = new ArrayList<>();
        boolean[] visited = new boolean[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            visited[ i ] = false;
        }
        int[] times = nodeTimes(visited);
        for (int i = 0; i < vertexNums; i++) {
            for (int j = 0; j < vertexNums; j++) {
                if (times[ j ] == 0 && !visited[ j ]) {
                    list.add(nodes[ j ]);
                    visited[ j ] = true;
                }
            }
            times = nodeTimes(visited);
        }
        return list;
    }

    private int[] nodeTimes(boolean[] status) {
        AceNode ace;
        int[] linkages = new int[ vertexNums ];
        for (int i = 0; i < vertexNums; i++) {
            linkages[ i ] = 0;
        }
        for (int i = 0; i < vertexNums; i++) {
            if (!status[ i ]) {
                ace = nodes[ i ].firstAce;
                while (ace != null) {
                    linkages[ ace.vNode.nodeNo ]++;
                    ace = ace.nextAce;
                }
            }
        }
        return linkages;
    }

}
